//
//  51_N皇后.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/3.
//

import UIKit

class PlaceQueens {
    
    var colums: [Int] = []
    var placeCount = 0
    func solveNQueens(_ n: Int) {
        colums = Array(repeating: -1, count: n)
        place(0)
        print("用有\(placeCount)种摆放方式")
    }
    func place(_ row: Int) {
        if row == colums.count {
            print(colums)
            placeCount += 1
            return
        }
//      回溯
        for colum in 0..<colums.count {
            if isAble(row, colum) {
                colums[row] = colum
                place(row + 1)
            }
        }
    }
    
    /// 当前位置都否可以摆放
    /// - Parameters:
    ///   - row: 行
    ///   - colum: 列
    /// - Returns: 结果
    func isAble(_ row: Int, _ colum: Int) -> Bool {
        for index in 0..<row {
//          判断列上是否有皇后
            if colums[index] == colum {
                return false
            }
//            斜线上是否有皇后
            if isXielv(row, index, colum, colums[index]){
                return false
            }
        }
        return true
    }
    
    /// 是否在斜线上
    /// - Parameters:
    func isXielv(_ x1: Int, _ x2: Int, _ y1: Int, _ y2: Int) -> Bool {
        abs(x1 - x2) == abs(y1 - y2)
    }
}

extension PlaceQueens {
    static func QA() {
        PlaceQueens().solveNQueens(4) // 4皇后有2种
        PlaceQueens().solveNQueens(8) // 8皇后有92种

    }
}
